#include <stdio.h>

void ShellSort(int* a, int n)
{
	int gap = n;

	while(gap > 1)
	{
		gap /= 2;
		
		int j = 0;
		for (j = 0; j < gap; j++)
		{
			int i = 0;
			for (i = j; i < n - gap; i += gap)
			{
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (tmp < a[end])
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}
	}
}

//void ShellSort(int* a, int n)
//{
//	int gap = n;
//	while (gap > 1)
//	{
//		//gap = gap / 2;
//		gap = gap / 3 + 1;
//		
//		int i = 0;
//		for (i = 0; i < n - gap; ++i)
//		{
//			int end = i;
//			int tmp = a[end + gap];
//			while (end >= 0)
//			{
//				if (tmp < a[end])
//				{
//					a[end + gap] = a[end];
//					end -= gap;
//				}
//				else
//				{
//					break;
//				}
//			}
//			a[end + gap] = tmp;
//		}
//	}
//}

int main()
{
	int arr[] = { 5,4,1,6,8,9,7,2,3,0 };
	
	ShellSort(arr,10);
	
	int i = 0;
	while(i < sizeof(arr)/sizeof(int))
	{
		printf("%d ",arr[i]);
		i++;
	}
	
	return 0;
}



